package Offer.q14_alienOrder;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class Solution {
    public String alienOrder(String[] words) {
        int n = words.length;
        int[] inDegree = new int[26]; // 入度表
        List<List<Integer>> adjTable = new ArrayList<>(); // 邻接表

        for (int i = 0; i < 26; i++) {
            inDegree[i] = -1; // 初始化入度表
            adjTable.add(new ArrayList<>()); // 初始化邻接表
        }

        for (String word : words) {
            for (int i = 0; i < word.length(); i++) {
                inDegree[word.charAt(i) - 'a'] = 0; // 出现的字母将入度更改为0
            }
        }
        // 我们只需相邻的两个字符串建立邻接关系
        // 不用两两建立
        for (int i = 0; i < n - 1; i++) {
            String s = words[i];
            String t = words[i + 1];
            //为了判断第二种情况，找出相邻两个字符串的长度最小值
            int m = Math.min(s.length(), t.length());
            for (int j = 0; j < m; j++) {
                int from = s.charAt(j) - 'a';
                int to = t.charAt(j) - 'a';
                // 出现不同 直接构建邻接关系和入度关系
                // 题目说过排序了，我们将前面一个字符串第一个不同的字符作为from
                // 将后面一个字符串第一个不同的字符作为to
                // 构建邻接关系
                if (from != to) {
                    adjTable.get(from).add(to);
                    inDegree[to]++;
                    break;
                    //和第二种情况违背，返回""
                } else if (j == m - 1 && s.length() > t.length()) {
                    return "";
                }
            }
        }

        //经典拓扑排序
        StringBuilder sb = new StringBuilder();
        Queue<Integer> queue = new ArrayDeque<>();
        int cnt = 0;
        for (int i = 0; i < 26; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
            //统计出现了多少个不同字母
            if (inDegree[i] != -1) {
                cnt++;
            }
        }
        while (!queue.isEmpty()) {
            int temp = queue.poll();
            sb.append((char)(temp + 'a'));
            for (int cour : adjTable.get(temp)) {
                inDegree[cour]--;
                if (inDegree[cour] == 0) {
                    queue.add(cour);
                }
            }
        }
        //如果构建的字符串长度不等于出现的字符种类数，返回""
        if (cnt != sb.length()) {
            return "";
        }
        return sb.toString();
    }

}
